func numTrees(n int) int {
    /*
        1. 确定dp数组的含义
            dp[i]表示n个节点组成的互不相同的二叉搜索树有n种
        2. 确定递推公式
            dp[3] = 一开头的头节点的二叉树数量 + 二开头的二叉树数量 + 三开头的二叉树数量
            一开头的二叉树数量 = 右子树的数量*左子树的数量  1 * dp[2]
            二开头的二叉树数量 = 右子树的数量*左子树的数量  dp[1] * dp[1]
            三开头的二叉树数量 = 右子树的数量*左子树的数量   dp[2] * 1
            将空二叉树的排列方式定义为1，所以
            所以：dp[3] = dp[0]*dp[2] + dp[1]*dp[1] + dp[2]*dp[0]
            递推公式：
                dp[i] = dp[0]dp[i-1] + dp[1]dp[i-3] + ... + dp[i-1]dp[0]
        3. 初始化dp数组
            dp[0] = 1
            dp[1] = 1
            dp[2] = 2
        4. 确定遍历顺序
            从前向后生成
        5. 得出动态数组
    */
    dp := make([]int, n+1)
    dp[0] = 1
    for i:=1; i<=n; i++ {
        for j:=1; j<=i; j++ {
            dp[i] += dp[j-1]*dp[i-j]
        }
    }
    return dp[n]
}